`\color{green} ✍️` A trader was moving along a road selling eggs. An idler who didn’t have much work to do, started to get the trader into a wordy duel. This grew into a fight, he pulled the basket with eggs and dashed it on the floor. The eggs broke. The trader requested the Panchayat to ask the idler to pay for the broken eggs. The Panchayat asked the trader how many eggs were broken. He gave the following response:
`" "color(green)" If counted in pairs, one will remain;"`
`" "color(green)" If counted in threes, two will remain;"`
`" "color(green)" If counted in fours, three will remain;"`
`" "color(green)" If counted in fives, four will remain;"`
`" "color(green)" If counted in sixes, five will remain;"`
`" "color(green)" If counted in sevens, nothing will remain;"`
`" "color(green)" My basket cannot accomodate more than 150 eggs."`
So, how many eggs were there? Let us try and solve the puzzle. Let the number of eggs be a. Then working backwards, we see that a is less than or equal to 150:
If counted in sevens, nothing will remain, which translates to `a = 7p + 0,` for some natural number `p`. If counted in sixes, `a = 6q+5,` for some natural number q.
If counted in fives, four will remain. It translates to `a = 5w + 4,` for some natural number `w.`
If counted in fours, three will remain. It translates to `a = 4s + 3,` for some natural number `s.`
If counted in threes, two will remain. It translates to `a = 3t + 2,` for some natural number `t.`
If counted in pairs, one will remain. It translates to `a = 2u + 1,` for some natural number `u.`
That is, in each case, we have `a` and a positive integer `b` (in our example, b takes values `7, 6, 5, 4, 3` and `2`, respectively) which divides `a` and leaves a remainder `r` (in our case,` r` is `0, 5, 4, 3, 2` and `1`, respectively), that is smaller than `b`.
The moment we write down such equations we are using Euclid’s division lemma,
Getting back to our puzzle, do you have any idea how you will solve it? Yes! You must look for the multiples of 7 which satisfy all the conditions. By trial and error
(using the concept of LCM), you will find he had 119 eggs.
`\color{green} ✍️` In order to get a feel for what Euclid’s division lemma is, consider the following pairs of integers:
`17, \ \ \ 6; \ \ \ 5, \ \ \ 12; \ \ \ 20, \ \ \ 4`
Like we did in the example, we can write the following relations for each such pair:
`17 = 6 × 2 + 5` (6 goes into 17 twice and leaves a remainder 5)
`5 = 12 × 0 + 5` (This relation holds since 12 is larger than 5)
`20 = 4 × 5 + 0` (Here 4 goes into 20 five-times and leaves no remainder)
That is, for each pair of positive integers a and b, we have found whole numbers `q` and `r,` satisfying the relation.
`\color{green} ✍️` `a = bq + r, 0 ≤ r < b`
Note that `q` or `r` can also be zero.
Why don’t you now try finding integers q and r for the following pairs of positive integers a and b?
`(i) 10, 3;" " (ii) 4, 19; " " (iii) 81, 3`
Did you notice that `q` and `r` are unique? These are the only integers satisfying the conditions `a = bq + r`, where `0 ≤ r < b`.
You may have also realised that this is nothing but a restatement of the long division process you have been doing all these years, and
that the integers q and r are called the quotient and remainder, respectively.
`\color{green} ✍️` `color(blue)(ul"A formal statement of this result is as follows :")`
`color(red)(★ ul"Theorem ( Euclid’s Division Lemma) :")` Given positive integers `a` and `b`, there exist unique integers `q` and `r` satisfying `a = bq + r, 0 ≤ r < b.`
This result was perhaps known for a long time, but was first recorded in Book VII of Euclid’s Elements. Euclid’s division algorithm is based on this lemma.
Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.
Recall that the HCF of two positive integers `a` and `b` is the largest positive integer `d` that divides both `a` and `b.`
`color(red)(=>"To obtain the HCF of two positive integers")`, say `c` and `d`, with `c > d`, follow the steps below:
`color(red)("Step 1 :")` Apply Euclid’s division lemma, to `c` and `d`. So, we find whole numbers, `q` and such that `color(blue)(c = dq + r,\ \ 0 ≤ r < d)`.
`color(red)("Step 2 :")` If `color(blue)(r = 0),\ \ d` is the HCF of `c` and `d`.
`" "` If `color(blue)(r ≠ 0,)` apply the division lemma to `d` and `r.`
`color(red)("Step 3 :")` Continue the process till the remainder is zero. The divisor at this stage will be the required `HCF.`
This algorithm works because `color(blue)(HCF (c, d) = HCF (d, r))` where the symbol `HCF (c, d)` denotes the `HCF` of `c` and `d,` etc.
`color(red)(=>"Let us see how the algorithm works, through an example")`.
Suppose we need to find the `HCF` of the integers `455` and `42.` We start with the larger integer, that is, `455.`
Then we use Euclid’s lemma to get
` " " 455 =42 xx 10+35`
Now consider the divisor `42` and the remainder `35,` and apply the division lemma to get
`" " 42 = 35 × 1 + 7`
Now consider the divisor `35` and the remainder `7`, and apply the division lemma to get
`" " 35 = 7 × 5 + 0`
Notice that the remainder has become zero, and we cannot proceed any further.
We claim that the HCF of `455` and `42` is the divisor at this stage, i.e., `7.`
You can easily verify this by listing all the factors of `455` and `42.` Why does this method work? It works because of the following result.
So, let us state Euclid’s division algorithm clearly.
`\color{green} ✍️` A trader was moving along a road selling eggs. An idler who didn’t have much work to do, started to get the trader into a wordy duel. This grew into a fight, he pulled the basket with eggs and dashed it on the floor. The eggs broke. The trader requested the Panchayat to ask the idler to pay for the broken eggs. The Panchayat asked the trader how many eggs were broken. He gave the following response:
`" "color(green)" If counted in pairs, one will remain;"`
`" "color(green)" If counted in threes, two will remain;"`
`" "color(green)" If counted in fours, three will remain;"`
`" "color(green)" If counted in fives, four will remain;"`
`" "color(green)" If counted in sixes, five will remain;"`
`" "color(green)" If counted in sevens, nothing will remain;"`
`" "color(green)" My basket cannot accomodate more than 150 eggs."`
So, how many eggs were there? Let us try and solve the puzzle. Let the number of eggs be a. Then working backwards, we see that a is less than or equal to 150:
If counted in sevens, nothing will remain, which translates to `a = 7p + 0,` for some natural number `p`. If counted in sixes, `a = 6q+5,` for some natural number q.
If counted in fives, four will remain. It translates to `a = 5w + 4,` for some natural number `w.`
If counted in fours, three will remain. It translates to `a = 4s + 3,` for some natural number `s.`
If counted in threes, two will remain. It translates to `a = 3t + 2,` for some natural number `t.`
If counted in pairs, one will remain. It translates to `a = 2u + 1,` for some natural number `u.`
That is, in each case, we have `a` and a positive integer `b` (in our example, b takes values `7, 6, 5, 4, 3` and `2`, respectively) which divides `a` and leaves a remainder `r` (in our case,` r` is `0, 5, 4, 3, 2` and `1`, respectively), that is smaller than `b`.
The moment we write down such equations we are using Euclid’s division lemma,
Getting back to our puzzle, do you have any idea how you will solve it? Yes! You must look for the multiples of 7 which satisfy all the conditions. By trial and error
(using the concept of LCM), you will find he had 119 eggs.
`\color{green} ✍️` In order to get a feel for what Euclid’s division lemma is, consider the following pairs of integers:
`17, \ \ \ 6; \ \ \ 5, \ \ \ 12; \ \ \ 20, \ \ \ 4`
Like we did in the example, we can write the following relations for each such pair:
`17 = 6 × 2 + 5` (6 goes into 17 twice and leaves a remainder 5)
`5 = 12 × 0 + 5` (This relation holds since 12 is larger than 5)
`20 = 4 × 5 + 0` (Here 4 goes into 20 five-times and leaves no remainder)
That is, for each pair of positive integers a and b, we have found whole numbers `q` and `r,` satisfying the relation.
`\color{green} ✍️` `a = bq + r, 0 ≤ r < b`
Note that `q` or `r` can also be zero.
Why don’t you now try finding integers q and r for the following pairs of positive integers a and b?
`(i) 10, 3;" " (ii) 4, 19; " " (iii) 81, 3`
Did you notice that `q` and `r` are unique? These are the only integers satisfying the conditions `a = bq + r`, where `0 ≤ r < b`.
You may have also realised that this is nothing but a restatement of the long division process you have been doing all these years, and
that the integers q and r are called the quotient and remainder, respectively.
`\color{green} ✍️` `color(blue)(ul"A formal statement of this result is as follows :")`
`color(red)(★ ul"Theorem ( Euclid’s Division Lemma) :")` Given positive integers `a` and `b`, there exist unique integers `q` and `r` satisfying `a = bq + r, 0 ≤ r < b.`
This result was perhaps known for a long time, but was first recorded in Book VII of Euclid’s Elements. Euclid’s division algorithm is based on this lemma.
Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.
Recall that the HCF of two positive integers `a` and `b` is the largest positive integer `d` that divides both `a` and `b.`
`color(red)(=>"To obtain the HCF of two positive integers")`, say `c` and `d`, with `c > d`, follow the steps below:
`color(red)("Step 1 :")` Apply Euclid’s division lemma, to `c` and `d`. So, we find whole numbers, `q` and such that `color(blue)(c = dq + r,\ \ 0 ≤ r < d)`.
`color(red)("Step 2 :")` If `color(blue)(r = 0),\ \ d` is the HCF of `c` and `d`.
`" "` If `color(blue)(r ≠ 0,)` apply the division lemma to `d` and `r.`
`color(red)("Step 3 :")` Continue the process till the remainder is zero. The divisor at this stage will be the required `HCF.`
This algorithm works because `color(blue)(HCF (c, d) = HCF (d, r))` where the symbol `HCF (c, d)` denotes the `HCF` of `c` and `d,` etc.
`color(red)(=>"Let us see how the algorithm works, through an example")`.
Suppose we need to find the `HCF` of the integers `455` and `42.` We start with the larger integer, that is, `455.`
Then we use Euclid’s lemma to get
` " " 455 =42 xx 10+35`
Now consider the divisor `42` and the remainder `35,` and apply the division lemma to get
`" " 42 = 35 × 1 + 7`
Now consider the divisor `35` and the remainder `7`, and apply the division lemma to get
`" " 35 = 7 × 5 + 0`
Notice that the remainder has become zero, and we cannot proceed any further.
We claim that the HCF of `455` and `42` is the divisor at this stage, i.e., `7.`
You can easily verify this by listing all the factors of `455` and `42.` Why does this method work? It works because of the following result.
So, let us state Euclid’s division algorithm clearly.